#include "node.h"
#include "table.h"
#include <stdlib.h>
#include <assert.h>
#include <string.h>
// 表的数据
const uint32_t ID_SIZE = size_of_attribute(Row, id); // id的大小
const uint32_t USERNAME_SIZE = size_of_attribute(Row, username);
const uint32_t EMAIL_SIZE = size_of_attribute(Row, email);
const uint32_t ROW_SIZE = ID_SIZE + USERNAME_SIZE + EMAIL_SIZE;

const uint32_t ID_OFFSET = 0;
const uint32_t USERNAME_OFFSET = ID_SIZE;
const uint32_t EMAIL_OFFSET = USERNAME_SIZE + USERNAME_OFFSET;

const uint32_t PAGE_SIZE = 4096;

#define TABLE_MAX_PAGES 100
const uint32_t ROWS_PRE_PAGE = PAGE_SIZE / ROW_SIZE;
const uint32_t TABLE_MAX_ROWS = ROWS_PRE_PAGE * TABLE_MAX_PAGES;

// 节点数据
const uint32_t NODE_TYPE_SIZE = sizeof(uint8_t);
const uint32_t NODE_TYPE_OFFSET = 0;
const uint32_t IS_ROOT_SIZE = sizeof(uint8_t);
const uint32_t IS_ROOT_OFFSET = NODE_TYPE_SIZE;
const uint32_t PARENT_POINTER_SIZE = sizeof(uint32_t);
const uint32_t PARENT_POINTER_OFFSET = IS_ROOT_OFFSET + IS_ROOT_SIZE;
const uint8_t COMMON_NODE_HEADER_SIZE =
    NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE;

// 叶节点数据
const uint32_t LEAF_NODE_NUM_CELLS_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_NUM_CELLS_OFFSET = COMMON_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_NEXT_LEAF_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_NEXT_LEAF_OFFSET =
    LEAF_NODE_NUM_CELLS_OFFSET + LEAF_NODE_NUM_CELLS_SIZE;
const uint32_t LEAF_NODE_HEADER_SIZE = COMMON_NODE_HEADER_SIZE +
                                       LEAF_NODE_NUM_CELLS_SIZE +
                                       LEAF_NODE_NEXT_LEAF_SIZE;

// 内部节点数据

const uint32_t LEAF_NODE_KEY_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_KEY_OFFSET = 0;
const uint32_t LEAF_NODE_VALUE_SIZE = ROW_SIZE;
const uint32_t LEAF_NODE_VALUE_OFFSET = LEAF_NODE_KEY_OFFSET + LEAF_NODE_KEY_SIZE;
const uint32_t LEAF_NODE_CELL_SIZE = LEAF_NODE_KEY_SIZE + LEAF_NODE_VALUE_SIZE;
const uint32_t LEAF_NODE_SPACE_FOR_CELLS = PAGE_SIZE - LEAF_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_MAX_CELLS =
    LEAF_NODE_SPACE_FOR_CELLS / LEAF_NODE_CELL_SIZE;

// 左节点最大的孩子的数量
const uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) / 2;
// 右节点最大的孩子数量ini
const uint32_t LEAF_NODE_LEFT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) - LEAF_NODE_RIGHT_SPLIT_COUNT;

// 返回table的根节点
void *get_table_root(Table *table)
{
    assert(table->pager != NULL);
    Node *node = get_page(table->pager, table->root_page_num);
    return node;
};

void initialize_leaf_node(Node *node)
{
    node->node_type = NODE_LEAF;
    node->num_cells = 0;
    node->is_root = false;
    node->next_leaf_page = 0;
    node->parent_pointer = 0;
};

void initialize_internal_node(Internal_Node *node)
{
    node->node_type = NODE_INTERNAL;
    node->num_keys = 0;
    node->is_root = false;
    node->parent_pointer = 0;
};

// 插入一行，在未满的时候
void leaf_node_insert(Cursor *cursor, uint32_t key, Row *value)
{
    // 找到对应的page
    Node *node = (Node *)get_page(cursor->table->pager, cursor->page_num);
    uint32_t max_key=get_node_max_key(node);
    if (node->num_cells >= LEAF_NODE_MAX_CELLS)
    {
        // 满了
        leaf_node_split_and_insert(cursor, key, value);
        return;
    }
    if (cursor->cell_num < node->num_cells)
    {
        // 将[cursor, cell_num) 都向后移动一位 然后将value给下标为cursor
        // 要加这个if 不然cursor->cell和cell_num相等的时候，uint32_t 就会出bug
        for (int i = node->num_cells - 1; i >= cursor->cell_num && i >= 0; i--)
        {
            memcpy(&node->rows[i + 1], &node->rows[i], LEAF_NODE_CELL_SIZE);
        }
    }

    node->rows[cursor->cell_num].key = key;
    node->num_cells += 1;
    serialize_row(value, &node->rows[cursor->cell_num].value);

    if (!node->is_root && max_key!=get_node_max_key(node))
    {
        // 更新父节点的最大值
        update_internal_node_key(cursor->table, node->parent_pointer, cursor->page_num);
    }
};

// 插入一行，在节点满了的时候
void leaf_node_split_and_insert(Cursor *cursor, uint32_t key, Row *value)
{
    Node *old_node = (Node *)get_page(cursor->table->pager, cursor->page_num);

    // 创建新的节点
    uint32_t new_node_page_num = get_unused_page_num(cursor->table->pager);
    Node *new_node = get_page(cursor->table->pager, new_node_page_num);
    // 初始化新的节点
    initialize_leaf_node(new_node);
    // 复制节点到新的位置
    for (int i = LEAF_NODE_MAX_CELLS; i >= 0; i--)
    {
        Leaf *destination;
        if (i >= LEAF_NODE_LEFT_SPLIT_COUNT)
        {
            // 复制到新的节点
            destination = &(new_node->rows[i % LEAF_NODE_LEFT_SPLIT_COUNT]);
        }
        else
        {
            // 复制到老的节点
            destination = &(old_node->rows[i]);
        }

        if (i == cursor->cell_num)
        {
            // 新的节点
            destination->key = key;
            serialize_row(value, &(destination->value));
        }
        else if (i > cursor->cell_num)
        {
            memcpy(destination, &(old_node->rows[i - 1]), LEAF_NODE_CELL_SIZE);
        }
        else
        {
            memcpy(destination, &(old_node->rows[i]), LEAF_NODE_CELL_SIZE);
        }
    }
    // 更新头节点信息
    new_node->is_root = false;
    new_node->node_type = NODE_LEAF;

    new_node->parent_pointer = old_node->parent_pointer;
    new_node->num_cells = LEAF_NODE_RIGHT_SPLIT_COUNT;

    old_node->num_cells = LEAF_NODE_LEFT_SPLIT_COUNT;
    old_node->next_leaf_page = new_node_page_num;

    // 判断原来的节点是不是根节点
    if (old_node->is_root)
    {
        create_new_root(cursor->table, new_node_page_num);
    }
    else
    {
        update_internal_node_key(cursor->table, old_node->parent_pointer, cursor->page_num);
        internal_node_insert(cursor->table, old_node->parent_pointer, new_node_page_num);
    }
}

// 创建新节点
void create_new_root(Table *table, uint32_t right_child_page_num)
{
    // 这时候，table的root是左孩子，参数是右孩子的page_num
    // 将左孩子移动到新的页面，左孩子原来的页面变成root即可
    uint32_t new_left_child_page_num = get_unused_page_num(table->pager);
    // 也有可能是叶节点，但是布局是一样的，也是无所谓的
    Node *left_child = (Node *)get_page(table->pager, new_left_child_page_num);
    Internal_Node *root = (Internal_Node *)get_table_root(table);

    memcpy(left_child, root, PAGE_SIZE);

    // 初始化新的根节点
    initialize_internal_node(root);
    left_child->is_root = false;
    left_child->parent_pointer = table->root_page_num;

    Node *right_child = (Node *)get_page(table->pager, right_child_page_num);
    right_child->parent_pointer = table->root_page_num;
    right_child->is_root = false;

    root->is_root = true;
    root->node_type = NODE_INTERNAL;
    root->num_keys = 1;

    root->internal_leaf[0].child_page = new_left_child_page_num;
    root->internal_leaf[0].key = get_node_max_key(get_page(table->pager, new_left_child_page_num));
    root->internal_leaf[1].child_page = right_child_page_num;
    root->internal_leaf[1].key = get_node_max_key(get_page(table->pager, right_child_page_num));
};

Cursor *leaf_node_find(Table *table, uint32_t page_num, uint32_t key)
{
    // 结果
    Cursor *result = malloc(sizeof(Cursor));

    Node *node = get_page(table->pager, page_num);
    int left = 0, right = node->num_cells - 1, mid;

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (node->rows[mid].key < key)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    // mid是第一个不大于key的下标

    result->cell_num = left;
    result->page_num = page_num;
    result->end_of_table = (result->cell_num == node->num_cells);
    result->table = table;
    return result;
};

Cursor *internal_node_find(Table *table, uint32_t page_num, uint32_t key)
{
    Internal_Node *internal_node = get_page(table->pager, page_num);
    int left = 0, right = internal_node->num_keys, mid;
    // 二分查找
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (internal_node->internal_leaf[mid].key < key)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    uint32_t result_page;
    if (left > internal_node->num_keys)
    {
        result_page = internal_node->internal_leaf[internal_node->num_keys].child_page;
    }
    else
    {
        result_page = internal_node->internal_leaf[left].child_page;
    }

    switch (get_node_type(get_page(table->pager, result_page)))
    {
    case NODE_LEAF:
        return leaf_node_find(table, result_page, key);
    case NODE_INTERNAL:
        return internal_node_find(table, result_page, key);
    default:
        break;
    }
};

NodeType get_node_type(void *node)
{
    // 获取节点数据
    uint8_t type = ((uint8_t *)node)[0];
    return type;
};

// 获取节点最大的key，用于标记索，-1表示空节点
uint32_t get_node_max_key(void *node)
{
    NodeType node_type = ((uint8_t *)node)[0];
    switch (node_type)
    {
    case NODE_INTERNAL:
        Internal_Node *internal_node = (Internal_Node *)node;
        if (internal_node->num_keys > 0)
        {
            // 返回最后一个节点的key
            return internal_node->internal_leaf[internal_node->num_keys].key;
        }
        else
        {
            return -1;
        }

    case NODE_LEAF:
        Node *leaf_node = (Node *)node;
        if (leaf_node->num_cells > 0)
        {
            return leaf_node->rows[leaf_node->num_cells - 1].key;
        }
        else
        {
            return -1;
        }

    default:
        printf("wrong node type\n");
        exit(EXIT_FAILURE);
        break;
    }
};

// 更新节点在父节点上最大的key
void update_internal_node_key(Table *table, uint32_t parent_num, uint32_t child_num)
{
    Internal_Node *parent_node = (Internal_Node *)get_page(table->pager, parent_num);
    Internal_Node *child_node = (Internal_Node *)get_page(table->pager, child_num);

    uint32_t new_child_key = get_node_max_key(child_node);
    for (int i = 0; i <= parent_node->num_keys; i++)
    {
        if (parent_node->internal_leaf[i].child_page == child_num)
        {
            parent_node->internal_leaf[i].key = new_child_key;
            if (!parent_node->is_root)
            {
                // 不是根节点，继续向上更新key
                update_internal_node_key(table, parent_node->parent_pointer, parent_num);
            }
            return;
        }
    }
    printf("wrong call there is no page_num %d in parent node\n", child_num);
    exit(EXIT_FAILURE);
};

// 插入一行，在节点没有满了的时候，内部节点
void internal_node_insert(Table *table, uint32_t parent_page_num, uint32_t child_page_num)
{ // parent_page_num就是要裂开或者添加节点的page_num
    Internal_Node *internal_node = (Internal_Node *)get_page(table->pager, parent_page_num);
    uint32_t max_key = get_node_max_key(internal_node);
    if (internal_node->num_keys >= INTERNAL_NODE_MAX_KEY - 1)
    {
        internal_node_split_and_insert(table, parent_page_num, child_page_num);
        return;
    }
    // 获取新节点的key，赋值父指针
    Node *child_node = get_page(table->pager, child_page_num);
    uint32_t new_key = get_node_max_key(child_node);
    child_node->parent_pointer = parent_page_num;

    for (int i = internal_node->num_keys; i >= 0; i--)
    {
        if (internal_node->internal_leaf[i].key > new_key)
        {
            internal_node->internal_leaf[i + 1].key = internal_node->internal_leaf[i].key;
            internal_node->internal_leaf[i + 1].child_page = internal_node->internal_leaf[i].child_page;
        }
        else
        {
            // 不会出现相等的情况
            assert(internal_node->internal_leaf[i].key != new_key);
            internal_node->internal_leaf[i + 1].key = new_key;
            internal_node->internal_leaf[i + 1].child_page = child_page_num;
            break;
        }
    }
    internal_node->num_keys++;
    if (max_key != get_node_max_key(internal_node) && !internal_node->is_root)
    {
        // 更新父节点的key
        update_internal_node_key(table, internal_node->parent_pointer, parent_page_num);
    }
};
//
void internal_node_split_and_insert(Table *table, uint32_t parent_page_num, uint32_t child_page_num)
{
    // parent_page_num是要插入的节点，他需要加入一个孩子，为child_page_num
    Internal_Node *old_node = (Internal_Node *)get_page(table->pager, parent_page_num);

    // 创建新的节点
    uint32_t new_node_page_num = get_unused_page_num(table->pager);
    Internal_Node *new_node = get_page(table->pager, new_node_page_num);
    Node *child_node = get_page(table->pager, child_page_num);
    uint32_t child_key = get_node_max_key(get_page(table->pager, child_page_num));
    // 初始化新的节点
    initialize_internal_node(new_node);
    // 找到应该插入的值的下标
    uint32_t insert_index = INTERNAL_NODE_MAX_KEY;
    for (int i = 0; i < INTERNAL_NODE_MAX_KEY; i++)
    {
        if (old_node->internal_leaf[i].key < child_key && child_key < old_node->internal_leaf[i + 1].key)
        {
            insert_index = i + 1;
            break;
        }
    }
    // 复制节点到新的位置
    for (int i = INTERNAL_NODE_MAX_KEY; i >= 0; i--)
    {
        Internal_Leaf *destination;
        if (i >= INTERNAL_NODE_LEFT_KEY)
        {
            // 复制到新的节点
            destination = &(new_node->internal_leaf[i % INTERNAL_NODE_LEFT_KEY]);
        }
        else
        {
            // 复制到老的节点
            destination = &(old_node->internal_leaf[i]);
        }

        if (i == insert_index)
        {
            // 新的节点
            destination->key = child_key;
            destination->child_page = child_page_num;
        }
        else if (i > insert_index)
        {
            destination->key = old_node->internal_leaf[i - 1].key;
            destination->child_page = old_node->internal_leaf[i - 1].child_page;
        }
        else
        {
            destination->key = old_node->internal_leaf[i].key;
            destination->child_page = old_node->internal_leaf[i].child_page;
        }
    }
    // 更新头节点信息
    new_node->is_root = false;
    new_node->node_type = NODE_INTERNAL;

    new_node->parent_pointer = old_node->parent_pointer;
    new_node->num_keys = INTERNAL_NODE_RIGHT_KEY - 1;

    // new_node的所有孩子，都需要更新其父节点指针
    for (int i = 0; i <= new_node->num_keys; i++)
    {
        Internal_Node *internal_node = (Internal_Node *)get_page(table->pager, new_node->internal_leaf[i].child_page);
        internal_node->parent_pointer = new_node_page_num;
    }

    old_node->num_keys = INTERNAL_NODE_LEFT_KEY - 1;

    // 判断原来的节点是不是根节点
    if (old_node->is_root)
    {
        create_new_root(table, new_node_page_num);
    }
    else
    {
        update_internal_node_key(table, old_node->parent_pointer, parent_page_num);
        internal_node_insert(table, old_node->parent_pointer, new_node_page_num);
    }
}